package violentRecursion;

import org.junit.Test;

/**
 * @author kunkun
 * @className LeetCode_322
 * @Description 零钱兑换
 * @date 2025/3/13 14:26
 */
public class LeetCode_322 {

    public int coinChange(int[] coins, int amount) {
//        Integer result = solution_1(coins, amount, 0);
//        return (result==null)?-1:result;
        Integer result = solution_2(coins, amount);
        return (result==null)?-1:result;
    }

    @Test
    public void test(){
        System.out.println(coinChange(new int[]{1,2,5}, 11));
    }

    //暴力递归
    private Integer solution_1(int[] coins, int amount,int i) {
        //1. 判断
        if (amount<0){
            return null;
        }
        if (amount==0){
            return 0;
        }
        if (amount!=0 && i==coins.length){
            return null;
        }

        //2. 对每种硬币循环
        int min = Integer.MAX_VALUE;
        int count =0;
        while (amount-coins[i]*count>=0){
            Integer result =solution_1(coins, amount-coins[i]*count,i+1);
            if (result!=null){
                result+=count;
                if (result<min){
                    min = result;
                }
            }
            count++;
        }
        return (min==Integer.MAX_VALUE)?null:min;
    }

    //动态规划
    private Integer solution_2(int[] coins, int amount) {
        //1. 定义结构，初始化值
        Integer[][] res = new Integer[coins.length+1][amount+1];
        for (int i = 0; i <= coins.length; i++) {
            res[i][0]=0;
        }
        for (int j = 1; j <= amount; j++) {
            res[coins.length][j]=null;
        }

        //2. 逐个循环
        for (int i = coins.length-1; i >=0 ; i--) {
            for (int j = 1; j <= amount; j++) {
                Integer min = null;
                int count =0;
                while (j-coins[i]*count>=0){
                    Integer result =res[i+1][j-coins[i]*count];
                    if (result!=null){
                        result+=count;
                        if (min==null || result<min){
                            min = result;
                        }
                    }
                    count++;
                }
                res[i][j]=min;
            }
        }
        return res[0][amount];




    }

}
